package com.leetcode.No0987;

import java.util.*;

/**
 * 	public class TreeNode {
 * 		int val;
 * 		TreeNode left;
 * 		TreeNode right;
 * 		TreeNode() {
 *      }
 * 		TreeNode(int val) {
 * 			this.val = val;
 *       }
 * 		TreeNode(int val, TreeNode left, TreeNode right) {
 * 			this.val = val;
 * 			this.left = left;
 * 			this.right = right;
 *      }
 *  }
 *
 * @program: leetcode
 * @description: 二叉树的垂序遍历
 * @author: wangzhihua
 * @date: 2021-08-03
 */
public class Solution01 {
	private HashMap<Integer, Set<MinNode>> map = new HashMap<>();

	public List<List<Integer>> verticalTraversal(TreeNode root) {
		dfs(root, 0, 0);
		return formatMinNode();
	}

	private void dfs(TreeNode node, int paramX, int paramY) {
		if (node == null) {
			return;
		}
		Set<MinNode> set = map.get(paramX);
		if (set == null) {
			set = getTreeSetInstance();
			map.put(paramX, set);
		}
		set.add(new MinNode(paramY, node.val));
		dfs(node.left, paramX - 1, paramY + 1);
		dfs(node.right, paramX + 1, paramY + 1);
	}

	private List<List<Integer>> formatMinNode() {
		Set<MinNode> set;
		ArrayList<Integer> list;
		List<List<Integer>> ansList = new ArrayList<>();
		for (int i = -1001; i <= 1001; ++i) {
			if ((set = map.get(i)) == null) {
				continue;
			}
			list = new ArrayList<>(set.size());
			for (MinNode node : set) {
				list.add(node.val);
			}
			ansList.add(list);
		}
		return ansList;
	}

	public TreeSet<MinNode> getTreeSetInstance() {
		return new TreeSet<MinNode>(new Comparator<MinNode>() {
			@Override
			public int compare(MinNode o1, MinNode o2) {
				if (o1.y != o2.y) {
					return o1.y - o2.y;
				}
				return (o1.val - o2.val == 0) ? 1 : (o1.val - o2.val);
			}
		});
	}

	private class MinNode {
		int y;
		int val;
		public MinNode() {}
		public MinNode(int y) {
			this.y = y;
		}
		public MinNode(int y, int val) {
			this.y = y;
			this.val = val;
		}
	}

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode() {
		}
		TreeNode(int val) {
			this.val = val;
		}
		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

}
